We discuss the following family of problems, parameterized by integers $C\geq2$ and $D\geq 1$: Does a given one-tape non-deterministic $q$-state Turingmachine make at most $Cn+D$ steps on all computations on all inputs of length$n$, for all $n$? Assuming a fixed tape and input alphabet, we show that these problems areco-NP-complete and we provide good non-deterministic and co-non-deterministiclower bounds. Specifically, these problems can not be solved in$o(q^{(C-1)/4})$ non-deterministic time by multi-tape Turing machines. We alsoshow that the complements of these problems can be solved in $O(q^{C+2})$non-deterministic time and not in $o(q^{(C-1)/2})$ non-deterministic time bymulti-tape Turing machines.
展开▼
机译：我们讨论以下由整数$ C \ geq2 $和$ D \ geq 1 $参数化的问题系列：给定的单带非确定性$ q $状态Turingmachine是否最多使所有步骤上的$ Cn + D $步对长度为$ n $的所有输入进行计算，对于所有$ n $？假定磁带和输入字母固定，我们证明这些问题是co-NP-完全的，并且提供了良好的不确定性和不确定性下界。具体地说，这些问题不能通过多带图灵机在不确定的时间内解决（o（q ^ {（C-1）/ 4}）$）。我们还表明，这些问题的补码可以在$ O（q ^ {C + 2}）$非确定性时间内解决，而不能在$ o（q ^ {（C-1）/ 2}）$非确定性时间内解决时间由多带图灵机完成。
展开▼
